Graham đăng ký đi lính Hải quân vào ngày 15 tháng 8 năm 1942 và được gửi tới trại tân binh tại San Diego, California trong sáu tuần. Sau đó anh được điều tới Trân Châu Cảng thuộc Oahu, Hawaii và được phân vào tàu USS South Dakota tháng 9.[5]

USS South Dakota

South Dakota rời Trân Châu Cảng vào ngày 16 tháng 10 năm 1942. Mười ngày sau, Graham tham chiến trong trận Santa Cruz. Nhờ công lao trong trận này, South Dakota và thủy thủ đoàn nhận được khen thưởng Navy Unit Commendation. Đêm ngày 14–15 tháng 11 năm 1942, Graham bị thương bởi đạn trái phá khi đưa một tin nhắn viết tay cho một sĩ quan trong trận hải chiến Guadalcanal. Thời điểm đó anh được giao nhiệm vụ nạp đạn cho một khẩu pháo phòng không 40 mm.[6][7] Mặc dù bị thương nhưng Graham vẫn góp phần trợ giúp và kéo các binh sĩ bị thương trên boong về nơi an toàn.[6] Anh nhận được Huân chương Sao Đồng và Trái tim Tím, còn tập thể tàu được nhận khen thưởng Navy Unit Commendation một lần nữa

South Dakota trở lại bờ đông vào ngày 18 tháng 12 năm 1942 để đại tu và sửa chữa các thiệt hại trong chiến tranh (tàu chịu 42 phát đạn từ ít nhất từ 3 tàu địch) tại Thành phố New York, và kể từ đó được đổi tên là "Battleship X" để khiến quân Nhật tưởng là tàu đã bị chìm. Mẹ của Graham tiết lộ tuổi của anh sau khi anh dự đám tang của bà mình (anh tới một ngày sau lễ tang) ở Texas mà không xin phép cấp trên. Anh bị giam ba tháng trong một khoang tàu tại Texas. Anh được thả sau khi chị anh đe dọa với phía Hải quân rằng sẽ mang chuyện này lên báo. Anh bị buộc giải ngũ vào ngày 1 tháng 4 năm 1943 mà không được hưởng trợ cấp hay tiền thưởng.[6][8][9]

Graham về sau làm thợ hàn trong một nhà máy quốc phòng chứ không đi học lại.[4]